| 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807 |
15x
659x
659x
1320x
659x
659x
741x
741x
741x
741x
17x
16x
1x
724x
13x
13x
711x
711x
324x
387x
15x
1296x
1004x
1004x
994x
10x
1004x
557x
557x
228x
228x
447x
447x
60x
60x
1004x
15x
1084x
15x
430x
419x
419x
419x
15x
15x
28331x
28331x
28331x
28331x
28331x
15x
15x
15x
22960x
15x
12079x
15x
45616x
15x
6266x
15x
5x
15x
446x
265x
181x
15x
118x
15x
16x
12x
4x
15x
5288x
5288x
5288x
914x
4374x
1018x
3356x
5288x
15x
220x
147x
73x
73x
73x
73x
15x
3259x
3259x
1390x
474x
1390x
1869x
1869x
324x
1869x
1196x
1049x
147x
147x
820x
2210x
15x
53908x
15x
7571x
7571x
7571x
7571x
7571x
15x
492x
492x
59x
59x
59x
492x
15x
324x
324x
44x
44x
324x
15x
1673x
1673x
15x
564x
564x
15x
2019x
2019x
2019x
15x
207x
207x
15x
10244x
10244x
10244x
10244x
10244x
15x
15x
15x
462x
15x
2865x
15x
182x
15x
13136x
15x
38024x
15x
12331x
15x
6x
15x
15x
15x
10451x
15x
19320x
15x
15x
15x
6081x
12227x
15x
3883x
15x
1231x
15x
24873x
24873x
32439x
32439x
13988x
18451x
6063x
12388x
12388x
10885x
15x
694x
694x
694x
1349x
1349x
694x
286x
286x
286x
408x
149x
259x
655x
415x
240x
240x
240x
15x
30124x
15x
848x
15x
118x
15x
12x
15x
6065x
15x
1x
15x
166x
15x
235x
15x
258x
15x
15x
| /**
* Copyright 2017 Google Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
/**
* @fileoverview Implementation of an immutable SortedMap using a Left-leaning
* Red-Black Tree, adapted from the implementation in Mugs
* (http://mads379.github.com/mugs/) by Mads Hartmann Jensen
* (mads379@gmail.com).
*
* Original paper on Left-leaning Red-Black Trees:
* http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf
*
* Invariant 1: No red node has a red child
* Invariant 2: Every leaf path has the same number of black nodes
* Invariant 3: Only the left child can be red (left leaning)
*/
// TODO: There are some improvements I'd like to make to improve memory / perf:
// * Create two prototypes, LLRedNode and LLBlackNode, instead of storing a
// color property in every node.
// TODO: It would also be good (and possibly necessary) to create a base
// interface for LLRBNode and LLRBEmptyNode.
export type Comparator<K> = (key1: K, key2: K) => number;
/**
* An iterator over an LLRBNode.
*/
export class SortedMapIterator<K, V, T> {
/** @private
* @type {Array.<!LLRBNode>}
*/
private nodeStack_: (LLRBNode<K, V> | LLRBEmptyNode<K, V>)[] = [];
/**
* @template K, V, T
* @param {LLRBNode|LLRBEmptyNode} node Node to iterate.
* @param {?K} startKey
* @param {function(K, K): number} comparator
* @param {boolean} isReverse_ Whether or not to iterate in reverse
* @param {(function(K, V):T)=} resultGenerator_
*/
constructor(
node: LLRBNode<K, V> | LLRBEmptyNode<K, V>,
startKey: K | null,
comparator: Comparator<K>,
private isReverse_: boolean,
private resultGenerator_: ((k: K, v: V) => T) | null = null
) {
let cmp = 1;
while (!node.isEmpty()) {
node = node as LLRBNode<K, V>;
cmp = startKey ? comparator(node.key, startKey) : 1;
// flip the comparison if we're going in reverse
if (isReverse_) cmp *= -1;
if (cmp < 0) {
// This node is less than our start key. ignore it
if (this.isReverse_) {
node = node.left;
} else {
node = node.right;
}
} else if (cmp === 0) {
// This node is exactly equal to our start key. Push it on the stack, but stop iterating;
this.nodeStack_.push(node);
break;
} else {
// This node is greater than our start key, add it to the stack and move to the next one
this.nodeStack_.push(node);
if (this.isReverse_) {
node = node.right;
} else {
node = node.left;
}
}
}
}
getNext(): T {
if (this.nodeStack_.length === 0) return null;
let node = this.nodeStack_.pop();
let result: T;
if (this.resultGenerator_)
result = this.resultGenerator_(node.key, node.value);
else result = { key: node.key, value: node.value } as any;
if (this.isReverse_) {
node = node.left;
while (!node.isEmpty()) {
this.nodeStack_.push(node);
node = node.right;
}
} else {
node = node.right;
while (!node.isEmpty()) {
this.nodeStack_.push(node);
node = node.left;
}
}
return result;
}
hasNext(): boolean {
return this.nodeStack_.length > 0;
}
peek(): T {
if (this.nodeStack_.length === 0) return null;
const node = this.nodeStack_[this.nodeStack_.length - 1];
Eif (this.resultGenerator_) {
return this.resultGenerator_(node.key, node.value);
} else {
return { key: node.key, value: node.value } as any;
}
}
}
/**
* Represents a node in a Left-leaning Red-Black tree.
*/
export class LLRBNode<K, V> {
color: boolean;
left: LLRBNode<K, V> | LLRBEmptyNode<K, V>;
right: LLRBNode<K, V> | LLRBEmptyNode<K, V>;
/**
* @template K, V
* @param {!K} key Key associated with this node.
* @param {!V} value Value associated with this node.
* @param {?boolean} color Whether this node is red.
* @param {?(LLRBNode|LLRBEmptyNode)=} left Left child.
* @param {?(LLRBNode|LLRBEmptyNode)=} right Right child.
*/
constructor(
public key: K,
public value: V,
color: boolean | null,
left?: LLRBNode<K, V> | LLRBEmptyNode<K, V> | null,
right?: LLRBNode<K, V> | LLRBEmptyNode<K, V> | null
) {
this.color = color != null ? color : LLRBNode.RED;
this.left =
left != null ? left : (SortedMap.EMPTY_NODE as LLRBEmptyNode<K, V>);
this.right =
right != null ? right : (SortedMap.EMPTY_NODE as LLRBEmptyNode<K, V>);
}
static RED = true;
static BLACK = false;
/**
* Returns a copy of the current node, optionally replacing pieces of it.
*
* @param {?K} key New key for the node, or null.
* @param {?V} value New value for the node, or null.
* @param {?boolean} color New color for the node, or null.
* @param {?LLRBNode|LLRBEmptyNode} left New left child for the node, or null.
* @param {?LLRBNode|LLRBEmptyNode} right New right child for the node, or null.
* @return {!LLRBNode} The node copy.
*/
copy(
key: K | null,
value: V | null,
color: boolean | null,
left: LLRBNode<K, V> | LLRBEmptyNode<K, V> | null,
right: LLRBNode<K, V> | LLRBEmptyNode<K, V> | null
): LLRBNode<K, V> {
return new LLRBNode(
key != null ? key : this.key,
value != null ? value : this.value,
color != null ? color : this.color,
left != null ? left : this.left,
right != null ? right : this.right
);
}
/**
* @return {number} The total number of nodes in the tree.
*/
count(): number {
return this.left.count() + 1 + this.right.count();
}
/**
* @return {boolean} True if the tree is empty.
*/
isEmpty(): boolean {
return false;
}
/**
* Traverses the tree in key order and calls the specified action function
* for each node.
*
* @param {function(!K, !V):*} action Callback function to be called for each
* node. If it returns true, traversal is aborted.
* @return {*} The first truthy value returned by action, or the last falsey
* value returned by action
*/
inorderTraversal(action: (k: K, v: V) => any): boolean {
return (
this.left.inorderTraversal(action) ||
action(this.key, this.value) ||
this.right.inorderTraversal(action)
);
}
/**
* Traverses the tree in reverse key order and calls the specified action function
* for each node.
*
* @param {function(!Object, !Object)} action Callback function to be called for each
* node. If it returns true, traversal is aborted.
* @return {*} True if traversal was aborted.
*/
reverseTraversal(action: (k: K, v: V) => void): boolean {
return (
this.right.reverseTraversal(action) ||
action(this.key, this.value) ||
this.left.reverseTraversal(action)
);
}
/**
* @return {!Object} The minimum node in the tree.
* @private
*/
private min_(): LLRBNode<K, V> {
if (this.left.isEmpty()) {
return this;
} else {
return (this.left as LLRBNode<K, V>).min_();
}
}
/**
* @return {!K} The maximum key in the tree.
*/
minKey(): K {
return this.min_().key;
}
/**
* @return {!K} The maximum key in the tree.
*/
maxKey(): K {
if (this.right.isEmpty()) {
return this.key;
} else {
return this.right.maxKey();
}
}
/**
*
* @param {!Object} key Key to insert.
* @param {!Object} value Value to insert.
* @param {Comparator} comparator Comparator.
* @return {!LLRBNode} New tree, with the key/value added.
*/
insert(key: K, value: V, comparator: Comparator<K>): LLRBNode<K, V> {
let cmp, n;
n = this;
cmp = comparator(key, n.key);
if (cmp < 0) {
n = n.copy(null, null, null, n.left.insert(key, value, comparator), null);
} else if (cmp === 0) {
n = n.copy(null, value, null, null, null);
} else {
n = n.copy(
null,
null,
null,
null,
n.right.insert(key, value, comparator)
);
}
return n.fixUp_();
}
/**
* @private
* @return {!LLRBNode|LLRBEmptyNode} New tree, with the minimum key removed.
*/
private removeMin_(): LLRBNode<K, V> | LLRBEmptyNode<K, V> {
if (this.left.isEmpty()) {
return SortedMap.EMPTY_NODE as LLRBEmptyNode<K, V>;
}
let n: LLRBNode<K, V> = this;
if (!n.left.isRed_() && !n.left.left.isRed_()) n = n.moveRedLeft_();
n = n.copy(null, null, null, (n.left as LLRBNode<K, V>).removeMin_(), null);
return n.fixUp_();
}
/**
* @param {!Object} key The key of the item to remove.
* @param {Comparator} comparator Comparator.
* @return {!LLRBNode|LLRBEmptyNode} New tree, with the specified item removed.
*/
remove(
key: K,
comparator: Comparator<K>
): LLRBNode<K, V> | LLRBEmptyNode<K, V> {
let n, smallest;
n = this;
if (comparator(key, n.key) < 0) {
if (!n.left.isEmpty() && !n.left.isRed_() && !n.left.left.isRed_()) {
n = n.moveRedLeft_();
}
n = n.copy(null, null, null, n.left.remove(key, comparator), null);
} else {
if (n.left.isRed_()) n = n.rotateRight_();
if (!n.right.isEmpty() && !n.right.isRed_() && !n.right.left.isRed_()) {
n = n.moveRedRight_();
}
if (comparator(key, n.key) === 0) {
if (n.right.isEmpty()) {
return SortedMap.EMPTY_NODE as LLRBEmptyNode<K, V>;
} else {
smallest = (n.right as LLRBNode<K, V>).min_();
n = n.copy(
smallest.key,
smallest.value,
null,
null,
(n.right as LLRBNode<K, V>).removeMin_()
);
}
}
n = n.copy(null, null, null, null, n.right.remove(key, comparator));
}
return n.fixUp_();
}
/**
* @private
* @return {boolean} Whether this is a RED node.
*/
isRed_(): boolean {
return this.color;
}
/**
* @private
* @return {!LLRBNode} New tree after performing any needed rotations.
*/
private fixUp_(): LLRBNode<K, V> {
let n = this as any;
if (n.right.isRed_() && !n.left.isRed_()) n = n.rotateLeft_();
if (n.left.isRed_() && n.left.left.isRed_()) n = n.rotateRight_();
if (n.left.isRed_() && n.right.isRed_()) n = n.colorFlip_();
return n;
}
/**
* @private
* @return {!LLRBNode} New tree, after moveRedLeft.
*/
private moveRedLeft_(): LLRBNode<K, V> {
let n = this.colorFlip_();
if (n.right.left.isRed_()) {
n = n.copy(
null,
null,
null,
null,
(n.right as LLRBNode<K, V>).rotateRight_()
);
n = n.rotateLeft_();
n = n.colorFlip_();
}
return n;
}
/**
* @private
* @return {!LLRBNode} New tree, after moveRedRight.
*/
private moveRedRight_(): LLRBNode<K, V> {
let n = this.colorFlip_();
if (n.left.left.isRed_()) {
n = n.rotateRight_();
n = n.colorFlip_();
}
return n;
}
/**
* @private
* @return {!LLRBNode} New tree, after rotateLeft.
*/
private rotateLeft_(): LLRBNode<K, V> {
const nl = this.copy(null, null, LLRBNode.RED, null, this.right.left);
return this.right.copy(null, null, this.color, nl, null) as LLRBNode<K, V>;
}
/**
* @private
* @return {!LLRBNode} New tree, after rotateRight.
*/
private rotateRight_(): LLRBNode<K, V> {
const nr = this.copy(null, null, LLRBNode.RED, this.left.right, null);
return this.left.copy(null, null, this.color, null, nr) as LLRBNode<K, V>;
}
/**
* @private
* @return {!LLRBNode} New tree, after colorFlip.
*/
private colorFlip_(): LLRBNode<K, V> {
const left = this.left.copy(null, null, !this.left.color, null, null);
const right = this.right.copy(null, null, !this.right.color, null, null);
return this.copy(null, null, !this.color, left, right);
}
/**
* For testing.
*
* @private
* @return {boolean} True if all is well.
*/
private checkMaxDepth_(): boolean {
const blackDepth = this.check_();
return Math.pow(2.0, blackDepth) <= this.count() + 1;
}
/**
* @private
* @return {number} Not sure what this returns exactly. :-).
*/
check_(): number {
let blackDepth;
Iif (this.isRed_() && this.left.isRed_()) {
throw new Error(
'Red node has red child(' + this.key + ',' + this.value + ')'
);
}
Iif (this.right.isRed_()) {
throw new Error(
'Right child of (' + this.key + ',' + this.value + ') is red'
);
}
blackDepth = this.left.check_();
Iif (blackDepth !== this.right.check_()) {
throw new Error('Black depths differ');
} else {
return blackDepth + (this.isRed_() ? 0 : 1);
}
}
}
/**
* Represents an empty node (a leaf node in the Red-Black Tree).
*/
export class LLRBEmptyNode<K, V> {
key: K;
value: V;
left: LLRBNode<K, V> | LLRBEmptyNode<K, V>;
right: LLRBNode<K, V> | LLRBEmptyNode<K, V>;
color: boolean;
/**
* Returns a copy of the current node.
*
* @return {!LLRBEmptyNode} The node copy.
*/
copy(
key: K | null,
value: V | null,
color: boolean | null,
left: LLRBNode<K, V> | LLRBEmptyNode<K, V> | null,
right: LLRBNode<K, V> | LLRBEmptyNode<K, V> | null
): LLRBEmptyNode<K, V> {
return this;
}
/**
* Returns a copy of the tree, with the specified key/value added.
*
* @param {!K} key Key to be added.
* @param {!V} value Value to be added.
* @param {Comparator} comparator Comparator.
* @return {!LLRBNode} New tree, with item added.
*/
insert(key: K, value: V, comparator: Comparator<K>): LLRBNode<K, V> {
return new LLRBNode(key, value, null);
}
/**
* Returns a copy of the tree, with the specified key removed.
*
* @param {!K} key The key to remove.
* @param {Comparator} comparator Comparator.
* @return {!LLRBEmptyNode} New tree, with item removed.
*/
remove(key: K, comparator: Comparator<K>): LLRBEmptyNode<K, V> {
return this;
}
/**
* @return {number} The total number of nodes in the tree.
*/
count(): number {
return 0;
}
/**
* @return {boolean} True if the tree is empty.
*/
isEmpty(): boolean {
return true;
}
/**
* Traverses the tree in key order and calls the specified action function
* for each node.
*
* @param {function(!K, !V):*} action Callback function to be called for each
* node. If it returns true, traversal is aborted.
* @return {boolean} True if traversal was aborted.
*/
inorderTraversal(action: (k: K, v: V) => any): boolean {
return false;
}
/**
* Traverses the tree in reverse key order and calls the specified action function
* for each node.
*
* @param {function(!K, !V)} action Callback function to be called for each
* node. If it returns true, traversal is aborted.
* @return {boolean} True if traversal was aborted.
*/
reverseTraversal(action: (k: K, v: V) => void): boolean {
return false;
}
/**
* @return {null}
*/
minKey(): null {
return null;
}
/**
* @return {null}
*/
maxKey(): null {
return null;
}
/**
* @private
* @return {number} Not sure what this returns exactly. :-).
*/
check_(): number {
return 0;
}
/**
* @private
* @return {boolean} Whether this node is red.
*/
isRed_() {
return false;
}
}
/**
* An immutable sorted map implementation, based on a Left-leaning Red-Black
* tree.
*/
export class SortedMap<K, V> {
/**
* Always use the same empty node, to reduce memory.
* @const
*/
static EMPTY_NODE = new LLRBEmptyNode();
/**
* @template K, V
* @param {function(K, K):number} comparator_ Key comparator.
* @param {LLRBNode=} root_ (Optional) Root node for the map.
*/
constructor(
private comparator_: Comparator<K>,
private root_:
| LLRBNode<K, V>
| LLRBEmptyNode<K, V> = SortedMap.EMPTY_NODE as LLRBEmptyNode<K, V>
) {}
/**
* Returns a copy of the map, with the specified key/value added or replaced.
* (TODO: We should perhaps rename this method to 'put')
*
* @param {!K} key Key to be added.
* @param {!V} value Value to be added.
* @return {!SortedMap.<K, V>} New map, with item added.
*/
insert(key: K, value: V): SortedMap<K, V> {
return new SortedMap(
this.comparator_,
this.root_
.insert(key, value, this.comparator_)
.copy(null, null, LLRBNode.BLACK, null, null)
);
}
/**
* Returns a copy of the map, with the specified key removed.
*
* @param {!K} key The key to remove.
* @return {!SortedMap.<K, V>} New map, with item removed.
*/
remove(key: K): SortedMap<K, V> {
return new SortedMap(
this.comparator_,
this.root_
.remove(key, this.comparator_)
.copy(null, null, LLRBNode.BLACK, null, null)
);
}
/**
* Returns the value of the node with the given key, or null.
*
* @param {!K} key The key to look up.
* @return {?V} The value of the node with the given key, or null if the
* key doesn't exist.
*/
get(key: K): V | null {
let cmp;
let node = this.root_;
while (!node.isEmpty()) {
cmp = this.comparator_(key, node.key);
if (cmp === 0) {
return node.value;
} else if (cmp < 0) {
node = node.left;
} else Eif (cmp > 0) {
node = node.right;
}
}
return null;
}
/**
* Returns the key of the item *before* the specified key, or null if key is the first item.
* @param {K} key The key to find the predecessor of
* @return {?K} The predecessor key.
*/
getPredecessorKey(key: K): K | null {
let cmp,
node = this.root_,
rightParent = null;
while (!node.isEmpty()) {
cmp = this.comparator_(key, node.key);
if (cmp === 0) {
if (!node.left.isEmpty()) {
node = node.left;
while (!node.right.isEmpty()) node = node.right;
return node.key;
} else if (rightParent) {
return rightParent.key;
} else {
return null; // first item.
}
} else if (cmp < 0) {
node = node.left;
} else Eif (cmp > 0) {
rightParent = node;
node = node.right;
}
}
throw new Error(
'Attempted to find predecessor key for a nonexistent key. What gives?'
);
}
/**
* @return {boolean} True if the map is empty.
*/
isEmpty(): boolean {
return this.root_.isEmpty();
}
/**
* @return {number} The total number of nodes in the map.
*/
count(): number {
return this.root_.count();
}
/**
* @return {?K} The minimum key in the map.
*/
minKey(): K | null {
return this.root_.minKey();
}
/**
* @return {?K} The maximum key in the map.
*/
maxKey(): K | null {
return this.root_.maxKey();
}
/**
* Traverses the map in key order and calls the specified action function
* for each key/value pair.
*
* @param {function(!K, !V):*} action Callback function to be called
* for each key/value pair. If action returns true, traversal is aborted.
* @return {*} The first truthy value returned by action, or the last falsey
* value returned by action
*/
inorderTraversal(action: (k: K, v: V) => any): boolean {
return this.root_.inorderTraversal(action);
}
/**
* Traverses the map in reverse key order and calls the specified action function
* for each key/value pair.
*
* @param {function(!Object, !Object)} action Callback function to be called
* for each key/value pair. If action returns true, traversal is aborted.
* @return {*} True if the traversal was aborted.
*/
reverseTraversal(action: (k: K, v: V) => void): boolean {
return this.root_.reverseTraversal(action);
}
/**
* Returns an iterator over the SortedMap.
* @template T
* @param {(function(K, V):T)=} resultGenerator
* @return {SortedMapIterator.<K, V, T>} The iterator.
*/
getIterator<T>(
resultGenerator?: (k: K, v: V) => T
): SortedMapIterator<K, V, T> {
return new SortedMapIterator(
this.root_,
null,
this.comparator_,
false,
resultGenerator
);
}
getIteratorFrom<T>(
key: K,
resultGenerator?: (k: K, v: V) => T
): SortedMapIterator<K, V, T> {
return new SortedMapIterator(
this.root_,
key,
this.comparator_,
false,
resultGenerator
);
}
getReverseIteratorFrom<T>(
key: K,
resultGenerator?: (k: K, v: V) => T
): SortedMapIterator<K, V, T> {
return new SortedMapIterator(
this.root_,
key,
this.comparator_,
true,
resultGenerator
);
}
getReverseIterator<T>(
resultGenerator?: (k: K, v: V) => T
): SortedMapIterator<K, V, T> {
return new SortedMapIterator(
this.root_,
null,
this.comparator_,
true,
resultGenerator
);
}
}
|